package com.company.OfferGuide;


import java.util.*;

public class 二叉搜索树与双向链表 {

    private List<Integer> list = new ArrayList<>();
    private HashMap<Integer,Node> hashMap = new HashMap<>();

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            list.add(node.val);
            hashMap.put(node.val,node);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        Collections.sort(list);
        Node head = hashMap.get(list.get(0));
        Node  p = head;
        for (int i = 1; i < list.size(); i++) {
            Node thisNode = hashMap.get(list.get(i));
            thisNode.left = p;
            p.right = thisNode;
            p = thisNode;
        }

        head.left = p;
        p.right = head;
        return head;

    }

}
